package com.fyl.leetcode.DFS;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author:fyl
 * @date 2021/5/18 14:29
 * @Modified By:
 * @Modified Date:
 * @Description:
 * 给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。
 *
 * 规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。
 *
 * 请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。
 * 给定下面的 5x5 矩阵:
 *
 *   太平洋 ~   ~   ~   ~   ~
 *        ~  1   2   2   3  (5) *
 *        ~  3   2   3  (4) (4) *
 *        ~  2   4  (5)  3   1  *
 *        ~ (6) (7)  1   4   5  *
 *        ~ (5)  1   1   2   4  *
 *           *   *   *   *   * 大西洋
 *
 * 返回:
 *
 * [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上图中带括号的单元).
 *
 * 1.找出所有从太平洋出发的水所能达到的点
 * 2.找出所有从大西洋出发的水所能达到的点
 * 3.这些重合的点便是我们要找的点
 */
public class PacificAtlantic {
    private int m;
    private int n;
    private final int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        List<List<Integer>> resList = new ArrayList<>();
        m = heights.length;
        n = heights[0].length;
        //大西洋
        boolean[][] atlantic = new boolean[m][n];
        //太平洋
        boolean[][] pacific = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            def(i, 0, pacific, heights);
            def(i, n - 1, atlantic, heights);
        }
        for (int i = 0; i < n; i++) {
            def(m - 1, i, atlantic, heights);
            def(0, i, pacific, heights);
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (atlantic[i][j] == pacific[i][j]) {
                    resList.add(Arrays.asList(i, j));
                }
            }
        }
        return resList;
    }

    private void def(int i, int j, boolean[][] canReach, int[][] matrix) {
        if (canReach[i][j]) return;
        canReach[i][j] = true;
        int nextR;
        int nextC;
        for (int[] dir : direction) {
            nextR = dir[0] + i;
            nextC = dir[1] + j;
            if (nextR < 0 || nextC < 0 || nextR >= m || nextC >= n || matrix[i][j] > matrix[nextR][nextC]) {
                continue;
            }
            def(nextR, nextC, canReach, matrix);
        }
    }
}
